package com.sourcetrip.algorithm.unionfind;

/**
 * @author: ZhouBert
 * @date: 2021/1/5
 * @description: 并查集（以 Quick Union 的思路实现）
 * --
 * 在【高度平衡】上，增加【路径压缩（Path Compression）】的优化
 * --
 * UnionFind 真是能玩出花来啊。
 * 优化思路：
 * 在 find() 时，对于寻找的路径上的元素一律指向根节点。
 * 但是，我发现此时 heightArray 中的元素失去了本来的意义，因为树的高度变矮了！！！
 * --
 * 数一数优化：
 * 1.QuickUnion （树化）；
 * 2.高度平衡；
 * 3.路径压缩（Path Compression）
 */
public class UnionFindWithQuickUnionV3 extends UnionFindWithQuickUnionV2 {
	/**
	 * 构建固定容量的并查集
	 * 默认初始 parents 的元素的根节点指向自身，这样表示每个元素都是独立的集合
	 *
	 * @param capacity 并查集的容量
	 */
	public UnionFindWithQuickUnionV3(int capacity) {
		super(capacity);
	}

	/**
	 * 基于 【按秩求并】的优化
	 * Path Compression
	 * @param v
	 * @return
	 */
	@Override
	protected int locate(int v) {
		//最后的根节点
		int root = super.locate(v);
		int res = v;
		int prev = res;
		while (parents[res] != res) {
			prev = res;
			res = parents[res];
			//将 res 的根节点修改 为 root
			parents[prev] = root;
		}
		return root;
	}
}
